data Tree a = Leaf a | Node (Tree a) a (Tree a)| Nil

igualdad::(Eq a) => Tree a -> Tree a -> Bool
igualdad Nil Nil = True
igualdad Nil _   = False
igualdad _ Nil   = False 
igualdad (Leaf x) (Leaf y) = x==y
igualdad (Node hi r hd)(Leaf y) = False
igualdad (Leaf x)(Node hi r hd) = False
igualdad (Node hi1 r1 hd1)(Node hi2 r2 hd2)
   | r1==r2 = igualdad hi1 hi2 && igualdad hd1 hd2
   | r1/=r2 = False 

instance (Eq a)=> Eq (Tree a) where
  t1 == t2 = igualdad t1 t2

instance (Show a) => Show (Tree a) where
   show (Nil)    = "( )"
   show (Leaf x) = show x
   show (Node hi r hd) = "<<"++show hi++" <-- @ "++ show r ++" @ --> "++show hd++">>"

flatten::Tree a -> [a]
flatten (Nil)    = [ ]
flatten (Leaf x) = [x]
flatten (Node x y z) = flatten x ++ [y] ++ flatten z

mapTree::(a->b)->Tree a->Tree b
mapTree  f (Nil) = Nil
mapTree  f (Leaf x) = Leaf (f x)
mapTree  f (Node hi r hd) = Node (mapTree f hi) (f r) (mapTree f hd)

bal::Tree a -> Bool
bal (Leaf x) = True
bal (Node x y z)
   | alt x == alt z = bal x && bal z
   | alt x /= alt z = False

maximo::Int->Int->Int
maximo x y
  | x >= y = x
  | otherwise = y  

alt::Tree a-> Int
alt (Nil)    = 0 
alt (Leaf x) = 1
alt (Node x y z) = 1 + maximo (alt x)(alt z)

size::Tree a-> Int
size (Nil)    = 0
size (Leaf x) = 1
size (Node x y z) = 1 + size x + size z


